package com.wxf.insertionSort;

import com.wxf.utils.CompareUtil;

public class InsertionSort {

    public static void low_sort(Comparable[] arr){
        int N = arr.length;
        for(int i = 1; i<N; i++){
            for(int j=i; j>=1 && CompareUtil.less(arr[j], arr[j-1]); j--){
                CompareUtil.exchange(arr, j, j-1); // 这里可以优化
            }
        }
    }

    public static void sort(Comparable[] arr){
        int N = arr.length;
        for(int i = 1; i<N; i++){
            Comparable key = arr[i];
            int j=i;
            for(; j>=1 && CompareUtil.less(arr[j], arr[j-1]); j--){
               arr[j] = arr[j-1]; // 这里可以优化
            }

            arr[j] = key;
        }
    }
}
